public class LeetCode96 {
    public int numTrees(int n) {
        // 初始化一个数组dp，大小为n+1，存储从Catalan数0到n的值
        int[] dp = new int[n + 1];

        // 基础情况：C_0 = 1
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            // 对于每个i，计算dp[i]的值
            for (int j = 0; j < i; j++) {
                // 根据Catalan数的递推公式：dp[i] += dp[j] * dp[i-j-1]
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }

}
